// 树形背包 选课
// https://www.luogu.com.cn/problem/P2014

int n, m;
int a[maxn];
vector<int> adj[maxn];
int f[maxn][max_size]; //表示在以 i 为根的子树中，选体积为 j 的最大价值

void dfs(int now) {
    f[now][1] = a[now];
    for (auto &p : adj[now]) {
        dfs(p);
        for (int j = m + 1; j >= 1; --j) { // 倒序枚举 j，保证 f[now][j - k] 是 f[now_pre][j - k]
            for (int k = 0; k < j; ++k) {  // 选择 now 是选择 p 子树的前提，所以 k < j
                f[now][j] = max(f[now][j], f[now][j - k] + f[p][k]);
            }
        }
    }
}
